package a10_动态规划;

/**
 * <p>
 * a09_不同的二叉搜索树
 * </p>
 *
 * @author flyduck
 * @since 2025/2/9
 */
public class a09_不同的二叉搜索树 {
    //n为3有多少情况=头节点为1+头节点为2+头节点为3
    //头节点为1 = 左子树有0个节点有多少种情况(1) * 右子树有2个节点有多少种情况(2)
    //头节点为2 = 左子树有1个节点有多少种情况(1) * 右子树有1个节点有多少种情况(1)
    //头节点为3 = 左子树有2个节点有多少种情况(2) * 右子树有0个节点有多少种情况(1)

    //dp[3] = dp[0] * dp[2] + dp[1] * dp[1] + dp[2] * dp[0]

    //dp[i]含义：i个节点总共有dp[i]种二叉树
    //递推公式：dp[i] = 头节点为1有多少种情况 + 头节点为2有多少种情况 + 头节点为3有多少种情况 + ... + 头节点为i有多少种情况
    //头节点为j有多少种情况=左子树有j-1个节点有多少种情况(dp[i-1]) * 右子树有i-j个节点有多少种情况(dp[i-j])
    public int numTrees(int n) {
        if(n <= 1){
            return 1;
        }
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] = dp[i] + dp[j-1] * dp[i-j];
            }
        }
        return dp[n];
    }
}
